In der letzten Woche mit Constraint-Satisfaction-Problemen angefangen

und die große Neuerung auf der konzeptionellen Ebene ist, dass wir zwar immer noch Suche machen,

aber letztlich die Zustände nicht mehr als Black Boxes begreifen. Also insbesondere haben

wir uns angeguckt, Arten wie man Zustände, man sollte da immer denken Weltzustände,

beschreiben kann und die Idee der Probleme, die wir lösen wollen, sind solche hier,

Scheduling-Probleme, Konfigurationsprobleme und so weiter, deren innere Struktur man gut

beschreiben kann und vor allen Dingen, wo man irgendwelche Regelsätze hat, die intendierten

Zustände, also die Zielzustände beschreiben kann. So ein Kalender, wie wir ihn da haben,

da will man auf jeden Fall, dass alle Mannschaften gegeneinander spielen, zweimal pro Saison,

einmal in der ersten Hälfte, einmal in der zweiten Hälfte. Man will außerdem nicht,

dass eine Mannschaft an zwei Orten zur gleichen Zeit sein muss, allerlei solche Dinge. Die

würde man ganz natürlich als Regeln über irgendwelche Variablen aufschreiben und genau

das machen wir hier. Statt dass wir Zustände haben, die Black Boxes sind, gucken wir uns

Regelsysteme an. Das ist die erste Art von Repräsentationssprache für die Umwelt, die

wir hier einsetzen und das ist eine relativ einfache und eine relativ allgemeine, mit dem

Erfolg, dass man dann auch relativ allgemeine Löser für diese Sachen bauen kann. Eben gerade

Constraintlöser. Und wir haben Constraint-Satisfaction-Probleme definiert, einfach als eine Menge von Variablen.

Jede Variable hat ihre Domäne der zulässigen Werte und man hat irgendwelche Constraints

und die Constraints werden einfach symmetrische Relationen sein. Symmetrische deswegen, weil

man da keine Richtung haben will. Typische Beispiele, Sudoku, wir haben Variablen für

jede Zelle eine, die haben alle die gleichen Domäne in diesem Fall und dann hat man Regeln,

so wie wir sie kennen, nämlich in jeder Spalte, Zeile und Diagonale darf keine Ziffer mehrfach

vorkommen und man muss sie alle verwenden. Unser Beispiel, was wir immer wieder verwenden,

ist die Dreifärbung von Australien. Im Allgemeinen braucht man vier, in diesem Fall kommt man

mit drei hin, weil es nur eine sehr kleine Karte ist und das ist lösbar. Wir haben hier

in diesem Fall sieben Variablen, jede Variable kriegt eine Farbe, also eine von dreien, die

Domäne ist sehr klein und wir haben die Constraints, dass zwei Territorien, die aneinanderstoßen

über eine nicht punktförmige Grenze, nicht die gleiche Farbe haben dürfen und das Problem

ist lösbar, da ist eine nützbar. Okay, die Runde Schläger haben wir uns angeguckt und

es ist so, dass wenn wir ganz normale Suchverfahren darauf anwenden wollen, dann haben wir ein

Problem, nämlich wir müssen Zustände haben, Zustände sind sehr viele und wir müssten

die irgendwie generieren und wir müssten natürlich einfach mit der Suche einen riesigen

Zustandsraum abklappern und das würde sehr lange dauern. Hier nutzen wir aus, dass wir

über die Zustände strukturell etwas aussagen können. Wir werden das heute sehen, was so

heuristisch ist, um das zu machen und man erreicht mehrere Größenordnungen an Speed-Up. Es ist

eigentlich wie immer in der KI-Vorlesung, wenn man irgendwelche Informationen hat, dann

kann man die ausnutzen. Informationen, entweder Heuristiken, so etwas wie die Luftlinienabstand

oder hier über die innere Struktur des Problems. Man muss allerdings fast immer einen Preis

zahlen und der Preis hier, den wir bezahlen, ist, dass wir die Probleme in einer bestimmten

Art und Weise aufschreiben müssen, nämlich über diese variablen Domänen-Constraints-Möglichkeiten.

Dass das in vielen Fällen sehr natürlich ist, ist ja sehr bequem. Aber im Prinzip

ist es so, dass wir die Probleme besser strukturieren müssen, damit wir die innere Struktur der

ganzen Sache herausarbeiten müssen. Bei sowas wie Australien oder Bundesliga ist das relativ

klar, wie wir an die interne Struktur kommen. Die springt einem förmlich entgegen oder

die sind die Regeln, die man erfüllen will. Aber manchmal zum Beispiel bei den Voltsproblemen,

nämlich solche Strichzeichnungen von unregelmäßigen Polyädern zu erkennen, da muss man erstmal

arbeiten, bis man das irgendwie in einer Constraint-Form hat. Hier ist es nicht so, dass es irgendwelche

Regeln gibt, in denen das Problem gegeben ist. Hier müssen wir uns die Regeln erstmal

bewegen. Das macht man so in diesem speziellen Fall, dass man irgendwie die Seiten orientiert

mit Plus, Minus und Größermarkiert. Und dann sind die Constraints, dass an beiden Seiten